package leetcode_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 2018年5月17日 下午4:54:54
 * @author 周杨
 * describe : 用回溯
 * SubsetsII_90 列举一个有重复数组里的所有子集  子集不能重复 AC 71%
 */
public class SubsetsII_90 {
	List<List<Integer>> res;
	int pre;
	int nums[];
	public static void main(String[] args) {
		SubsetsII_90 test=new SubsetsII_90();
		//test.subsetsWithDup(new int[]{1,1,2,2,3});
		//test.subsetsWithDup(new int[]{4,4,4,5,7,7,8});
		List<List<Integer>> result=test.subsetsWithDup1(new int[]{1,4,3,5,4,4,7,7,8,0});

	}
	
	/**
	 * @param nums 不知哪里出了问题
	 */
	public  List<List<Integer>> subsetsWithDup(int[] nums) {
		if(nums==null)
			return null;
		this.res=new ArrayList<List<Integer>>();
        this.nums=nums;
        this.pre=Integer.MIN_VALUE;
        this.res.add(new ArrayList<Integer>());
        Arrays.sort(nums);
        	for(int i=0;i<nums.length;++i)
        help(new ArrayList<Integer>(),i);
    	return this.res;
    }
	
	public void help(List<Integer> list,int index){
		if(pre!=this.nums[index]){//不等于回退的才可以列入
			list.add(nums[index]);
			List<Integer> now=new ArrayList<Integer>();
			now.addAll(list);
			this.res.add(now);
			for(int i=index+1;i<nums.length;++i)
				help(list,i);
			pre=nums[index];
			list.remove(list.size()-1);
		}
		else{//如果当前遍历的数字和之前回退的数字一样
			if(list.size()==0)//避免当前集合第一个数就不放的情况 后面不必判断
				return ;
			for(int i=index+1;i<nums.length;++i)
				help(list,i);
		}
	}
	
	/**
	 * describe:每次保存数的时候利用现有的res集合  从其中取子集合 然后构造新的集合 重复的数值直接用区间判断
	 * 2018年5月18日 下午1:54:56
	 */
	public List<List<Integer>> subsetsWithDup1(int[] nums) {
		final List<List<Integer>> res = new ArrayList<>();
	    Arrays.sort(nums);
	    res.add(new ArrayList<Integer>());
	    int l =0;
	    for(int i = 0; i < nums.length; i++){
	      int r = res.size();//确定右边界
	      if(i==0 || nums[i-1] !=nums[i] )  l = res.size();
	      //左边界为当前结果集里的个数 如果出现重复起始值 则不改变左边界 
	      //如果当前值不重复 则取最近的一个List 添加一个值
	      for(int j=r - l; j<r; j++){
	        List<Integer> subset = new ArrayList<>(res.get(j));
	        subset.add(nums[i]);
	        res.add(subset);
	      }
	    }
	    return res;
	  }
	

}
